package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/1
 * @Description: 插入排序
 * @version: 1.0
 */
public class InsertionSort {
    /*
     * 思路:将数组分成2部分，第一个元素为已经排好序的部分，后面的元素为未排好序的元素,按照规则将未
     * 排好序的元素插入到排好序的部分
     * 时间复杂度: 最好O(n^2)  最坏O(n^2)  平均O(n^2)
     * 空间复杂度:O(1)
     */
    public static int[] insertSort(int[] arr) {
        //从第二个元素开始遍历，进行排序
        for (int low = 1; low < arr.length; low++) {
            int t = arr[low];
            int i = low - 1;
            //从右边向左边找，如果比待插入元素大则要空出插入位置
            while (i >= 0 && arr[i] > t) {
                arr[i + 1] = arr[i];
                i--;
            }
            //找到插入位置
            if (i != low - 1) {
                arr[i + 1] = t;
            }
        }
        return arr;
    }
}
